#include "Quicksort.h"

DATA::DATA()
{
  index = -1;
  val = 0.0;
};

DATA::DATA(int _index, int _val,char* _word)
{
  index = _index;
  val = _val;
  word = _word;
};

  
int DATA::set_index(int _index)
{
  index = _index;
  return 0;
};

int DATA::set_val(int _val)
{
  val = _val;
  return 0;
};

int DATA::get_index()
{
  return index;
};

int DATA::get_val()
{
  return val;
};

char* DATA::get_word()
{
  return word;
};

/** 
 * Partitioning the array by val.
 * 
 * @param arr The pointer to the first element of the array.
 * @param _i  The index  of the first elements.
 * @param _j  The index  of the last elements.
 * 
 * @return The index of the pivot.
 */
int partition(std::vector<DATA> &arr, int _i, int _j);

/** 
 * Partitioning the array by index.
 * 
 * @param arr The pointer to the first element of the array.
 * @param _i  The index  of the first elements.
 * @param _j  The index  of the last elements.
 * 
 * @return The index of the pivot.
 */
int partition_index(std::vector<DATA> &arr, int _i, int _j);

/** 
 * An optimization for quicksort, when (j - i + 1) less than 3, we use 
 * direct method instead of recursion.
 * 
 * @param arr The pointer to the first element to sort.
 * @param _i The index of the first element.
 * @param _j The index of the last element.
 * 
 * @return Error code, 0 for OK.
 */
int opti_quicksort_index(std::vector<DATA> &arr, int _i, int _j);

/** 
 * An optimization for quicksort, when (j - i + 1) less than 3, we use 
 * direct method instead of recursion.
 * 
 * @param arr The pointer to the first element to sort.
 * @param _i The index of the first element.
 * @param _j The index of the last element.
 * 
 * @return Error code, 0 for OK.
 */
  int opti_quicksort(std::vector<DATA> &arr, int _i, int _j);
/**
 * Sort array arr again by index of the elements.
 *
 * @param arr The pointer to the first element to sort.
 * @param _i The index of the first element.
 * @param _j The index of the last element.
 * 
 * @return Error code, 0 for OK.
 */
int re_quicksort(std::vector<DATA> &arr, int _i, int _j);

/**
 * Sort array arr by stable quicksort.
 *
 * @param  &arr The address of array arr.
 *
 * @return Error code, 0 for OK.
 */
 int stable_quick_sort(std::vector<DATA> &arr);

int opti_quicksort(std::vector<DATA> &arr, int _i, int _j)
{
    if (_j - _i > 1)
    {
      int p = partition(arr, _i,_j);
      opti_quicksort(arr, _i, p - 1);
      opti_quicksort(arr, p + 1, _j);
      return 0;
    }
    else
    {
	if (_j - _i == 0)
	    return 0;
	else if( _j - _i == 1)
	  {
	    if (arr[_i].get_val() > arr[_j].get_val())
	      {
	    	DATA tmp = arr[_i];
		arr[_i] = arr[_j];
		arr[_j] = tmp;
	      }
	    return 0;
	  }
    }
};

int partition(std::vector<DATA> &arr, int _i, int _j)
{
    if (_j - _i <= 0)
	return 0;
    int left = _i;
    int right = _j;
    DATA pivot = arr[_i];
    while (left != right)
    {
	while (arr[right].get_val() >= pivot.get_val()
	       && right > left)
	    right--;
	while (arr[left].get_val() <= pivot.get_val()
	       && right > left)
	    left++;
	if (arr[left].get_val() > arr[right].get_val() && right > left)
	{	
	    DATA tmp = arr[left];
	    arr[left] = arr[right];
	    arr[right] = tmp;
	    right--;
	}
    }
    arr[_i] = arr[left];
    arr[left] = pivot;
    return left;
};

int partition_index(std::vector<DATA> &arr, int _i, int _j)
{
    if (_j - _i <= 0)
	return 0;
    int left = _i;
    int right = _j;
    DATA pivot = arr[_i];
    while (left != right)
    {
	while (arr[right].get_index() >= pivot.get_index()
	       && right > left)
	    right--;
	while (arr[left].get_index() <= pivot.get_index()
	       && right > left)
	    left++;
	if (arr[left].get_index() > arr[right].get_index() && right > left)
	{	
	    DATA tmp = arr[left];
	    arr[left] = arr[right];
	    arr[right] = tmp;
	    right--;
	}
    }
    arr[_i] = arr[left];
    arr[left] = pivot;
    return left;
};

int opti_quicksort_index(std::vector<DATA> &arr, int _i, int _j)
{
    if (_j - _i > 1)
    {
      int p = partition_index(arr, _i,_j);
      opti_quicksort_index(arr, _i, p - 1);
      opti_quicksort_index(arr, p + 1, _j);
      return 0;
    }
    else
    {
	if (_j - _i  == 0)
	    return 0;
	else if( _j - _i == 1)
	  {
	    if (arr[_i].get_index() > arr[_j].get_index())
	      {
	    	DATA tmp = arr[_i];
		arr[_i] = arr[_j];
		arr[_j] = tmp;
	      }
	    return 0;
	  }
    }
};

int re_quicksort(std::vector<DATA> &arr, int _i, int _j)
{
  for(int i = _i; i <=_j; )
    {
      int tmp = arr[i].get_val();
      int stop = i;
      while(arr[stop].get_val() == tmp && stop <= _j)
	{
	  stop++;
	}
      opti_quicksort_index(arr, i, stop - 1);
      i = stop;
    }
  return 0;
};

int stable_quick_sort(std::vector<DATA> &arr)
{
  opti_quicksort(arr, 0, arr.size() - 1);
  
  re_quicksort(arr, 0, arr.size() - 1);
  return 0;
};
/*
#include <string>

int main(int argc, char *argv[])
{
    int n = -1;
    std::cin >> n;
    std::string dummy;
    std::vector<DATA> arr;
    
    DATA data;
    double tmp;
    for( int i = 0; i < n; i++)
      {
	std::cin >> tmp;
	DATA A(i,tmp);
	arr.push_back(A);
      }   

    std::cout << "Before:" << std::endl;
  
    for(int i = 0; i < arr.size() ;i++)
    std::cout << "index = " << arr[i].get_index()
	 << ", value = " << arr[i].get_val() << std::endl;
    stable_quick_sort(arr);
    std::cout << "After:" << std::endl;
    for(int i = 0; i < arr.size() ;i++)
    std::cout << "index = " << arr[i].get_index()
	 << ", value = " << arr[i].get_val() << std::endl;
    
    return 0;
};
*/
